package xiaohongshu.com.sunny.t3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        boolean flag = true;
        while (m-->0){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if(a == b)
                flag = false;
            if(map.containsKey(a)){
                map.get(a).add(b);
            }else{
                ArrayList<Integer> list = new ArrayList<>();
                list.add(b);
                map.put(a, list);
            }
            if(map.containsKey(b)){
                map.get(b).add(a);
            }else{
                ArrayList<Integer> list = new ArrayList<>();
                list.add(a);
                map.put(b,list);
            }
        }
        if(!flag){
            System.out.println(0);
            return;
        }
        if(n == 0 || n == 1){
            System.out.println(0);
            return;
        }
        if(n == 2){
            System.out.println(1);
            return;
        }
        for(int a: map.keySet()){
            ArrayList<Integer> list = map.get(a);
            for(int i=0;i<list.size();i++){
                for(int j=i+1;j<list.size();j++){
                    if(list.get(i) - list.get(j) == 0)
                        continue;
                    if((map.containsKey(list.get(i)) && map.get(list.get(i)).contains(list.get(j))) ||
                            (map.containsKey(list.get(j)) && map.get(list.get(j)).contains(list.get(i)))){
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(flag)
            System.out.println(1);
        else
            System.out.println(0);
    }

}
